package com.temp;

/**
 * @Title: Search.java
 * @author fusz
 * @date 2011-12-19
 * @version
 */
public class Search {
	/**
	 * 递归查找一维数组
	 * @param data
	 * @param key
	 * @return
	 */
	public static boolean recursivelySearch(int[] data, int key) {
		if (searchIndex(data,key)<0)
		return false;
		return true;
	}
	private static int searchIndex(int[] data, int key) {
		if (data == null || data.length < 1)
		return -1;
		return doSearch(data, 0, data.length - 1, key);
	}
	private static int doSearch(int[] data, int low, int high,int key) {
		if (low > high)
			return -1;
		int mid = (low + high) / 2;
		if (key < data[mid]) {
			return doSearch(data, low, mid - 1, key);
		} else if (key > data[mid]) {
			return doSearch(data, mid + 1, high, key);
		} else {
			return mid;
		}
	}
	/**
	 * 二分查找一维数组
	 * @param data
	 * @param key
	 * @return
	 */
	public static boolean binarySearch(int[] data, int key){
		if(binarySearch(data, 0, data.length, key)<0)
			return false;
		return true;
	}
	public static int binarySearch(int[] a, int fromIndex, int toIndex,int key) {
		int low = fromIndex;
		int high = toIndex - 1;
		
		while (low <= high) {
		int mid = (low + high) >>> 1;
		int midVal = a[mid];
		
		if (midVal < key)
		low = mid + 1;
		else if (midVal > key)
		high = mid - 1;
		else
		return mid; // key found
		}
		return -(low + 1);  // key not found.
	}
}
